Let {an}n=0+∞ be a sequence of numbers, real or complex
A recurrence relation is a rule, or function, that defines the general term an in terms of one ore more of the preceding terms, a0,a1,…,an−1
That is, an=f(a0,a1,⋯,an−1),∀n=1,2,⋯
A solution of a recurrence relation is a sequence {an}n=0+∞ whose terms satisfy the recurrence relation
Recurrence relations can have more than one solution. To ensure that a recurrence relation has exactly one solution, we can specify initial conditions for our solution
These are just specific values for some terms a0,a1,…,an0 of a solution.
We will look at a number of examples to clarify these concepts
Example 1 The number of bacteria in a colony doubles every hour. If we initially have 5 bacteria to begin with, how many are there after 5 hours? after n hrs?
We start with 5 , so after
Time (hours)
Number of Bacteria
0
5
1
10
2
20
3
40
4
80
5
160
Now if we let an= number of bacteria after n hours, we have the recurrence relation
(i) an=2an−1,n=1,2,3⋯
with the initial condition
(ii) a0=5
Equations (i) a (ii) together form an "initial value recurrence relation" with a unique solution{an}x=0+∞ with a0=5.
Thus after n hours we have an bacteria where
an=2an−1a0=5
Example 2 Classical Example due to Leonardo di Pisa aka Fibonacci 13th century AD book "Liber Abaci" Italian for counting numbers where does the word abbacus comes from
A young pair of rabbits, I male, I female, are put on an island. A pair of rabbit can't breed until they are 2 months old. after they are 2 months old, each pain produces another pair each month. assuming no deaths "find the number of rabbits after the n month" (ie find a recurrence relation for these numbers)
To analyze the situation consider the following chart:
Month 123456 Reproducing 001123 Young Pairs 111235 Total Pairs 112358
Let fn= number pairs of rabbits after n months. We have f1=f2=1 since there is no breeding going on. That is each new pair comes from a pair at least 2 months old
To determine the recurrence relation we employ backwards reasoning.
Let n⩾3.
If the number of pairs in the nth month is fn, it is equal to the number of pairs in month n−1,fn−1, plus the number of new born pairs. The number of new born pairs is equal to the number of pairs at least 2 months old, ie fn−2,
Thus fn and f1f2=fn−1+fn−2,n=3,4,⋯=1=1
The recurrence relation with initial conditions (2) has a unique solution called\
The Fibonacci numbers (Fibonacci' Sequence)
A flight of stairs has n steps that one can climb one step at a time or two steps at a time. How many ways can one climb the stairs?
Let tn= number of ways to get to the nth step Our last step is either 1 step or 2 steps
Thus tn=tn−1+tn−2
Now
t1=1t2=2
And tn satisfies
tn=tn−1+tn−2t1=1t2=2⎭⎬⎫
and
J={1,2,3,5,8,13,⋯}
Clearly tx=fx+1 from example 2
Exercise Let an= number of bit strings of length n that do not have 2 consecutive zeros
Show a1=2,a2=3 and that an=fn+2=n+2nd Fibonacci number
Example 3 Suppose we have a computer system that considers a string of decimal digits a valid codeword if it has an even number of 0 digits. Fore example
120430900 valid 120430901 invalid
Let an= number of valid n digit codewords
Find a recurrence relation for an.
Fist note a1=9, since 0 is the only invalid I digit string.
How do we get a valid n-digit string from a string n−1 digit long.
2 ways:
i) append 1−9 onto a valid x−1 digit string in 9an−1 ways
ii) append 0 to an invalid x−1 digit sting
Now there are 10n−1n−1 digit strings of which an−1 are valid,
so there are 10n−1−an−1 invalid n−1 digit strings
Thus
an That is ana1=9⋅an−1+(10n−1−an−1),=8⋅an−1+10n−1,=9
The Recurrence Relation (1) - (4) give us information on how to calculate the general term an, using terms that came before, starting from our initial conditions
It can be impractical to calculate an from the recurrence relation, and we cant really investigate the long term behavior (as n→+∞ ).
If we can find a formula an=f(n) for the general term we call it a closed form of the solution
This method of finding a closed form solution (assuming it exists) of a recurrence relation is called iteration. It in not in general of much use.
It would be nice to be able to "write down" the closed solution of a recurrence relation. This is not possible for all recurrence relations but there is a special type we can solve in this manner, and actually say a lot about the possible solutions
Definition A linear homogeneous recurrence relation of degree k with constant coefficients is one of the form
(5)an=c1an−1+c2an−2+⋯+ckan−k,n⩾k
where c1,c2,⋯,ck are constants and ck=0,
linear: the R.H.S. of 5 is a linear combination of an−1,⋯,an−k
homogeneous: no terms that are not multiples of an−1,⋯,an−kso no n powers
constant coefficients: coefficients of an−1,⋯,qn−k don't depend on n
degree k:an depends on the previous k terms an−1,⋯,an−k
Of our examples so far
linear homogeneous, degree 1, const coefficients
linear homogeneous, degree 2, const coefficients
linear homogeneous, degree 2, const coefficients
linear non-homogeneous, degree 1, const coefficients
An example of a non-linear recurrence relation would be
an=an−1+an−22,
and an=nan−1+4an−2 is homogenous linear without constant coefficients
The study of linear recurrence relations relies heavily on the techniques of linear algebra
As this is a brief intro, we wont explore the theory in great detail but instead consider some basic results
The key to our development of closed solutions lies in our reconsideration of example (1)
There we found an=a0⋅2n and so let us look for solutions of 5 of the form
Notep(r)=rk−c1rk−1−⋯−ck is called the characteristic polynomial of the linear, homogenous, recurrence relation with constant coefficients an=c1an−1+⋯+ckan−k,ck=0 and an=a⋅rn is a solution of 5 iff P(r)=0
Facts
The zeros of p(r) determine all the solutions of 5
A recurrence relation of degree k has k-degrees of freedom
This means that there will be k arbitrary constants in a general solution of 5
For every initial condition we impose on a solution, we eliminate a degree of freedom/ ∴ 1 initial conditions ⇒ unique solution
(as we have seen in our examples)
(4)
The Principle of Superposition
Any linear combination of solutions of 5 is again a solution of 5
That is, if {an1},{an2},⋯,{an2} are solutions of 5 then so is
{a1an1+a2an2+⋯+a1anl},
This is because 5 is a linear homogeneous recurrence relation
We now turn our attention to 2nd order homogenous linear recurrence relations with constant coefficients because they are completely solvable, (Proofs omitted)
Let us suppose, c1,c2∈R are given constants,
an=c1an−1+c2an−2
The characteristic polynomial equation for above is
Then every solution of 7 is of the form an=a1r1n+a2r2n where a1,a2 are arbitrary real numbers. If we set 1 initial condition we will be able to write a2 in terms of a1. If we set 2 initial conditions we will determine a1,a2 uniquely
Example Let an=an−1+2an−2,n⩾2 (9)
The characteristic equation for (9) is r2−r−2=(r+1)(r−1)=0 Thusr1=−1,r2=2 and every solution of (9) has the form
an=a1(−1)n+a22n,n⩾0(10)
If we now impose the condition a0=1, we substitute n=0 in (10) to get
1=a1+a2 or a2=1−a1
and then
an=a1(−1)n+(1−a1)2n(11)
If we now insist that a1=−2, we substitute n=1 in (11) to get
−2=a1(−1)1+(1−a1)21=2−3a1
and 3a1=4⇒a1=34⋅(1−34=−31)
Thus an=34(−1)n−312n is the unique solution of the Initial Value recurrence relation (13)